package com.icbc.DataStructuresAndAlgorithms;


import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class StackDomo {
	private int a = 0;
	private static Map<String, Integer> map = new HashMap<>();
	static {
		map.put("+", 0);
		map.put("-", 0);
		map.put("*", 1);
		map.put("/", 1);
		map.put("(", 2);
		map.put(")", 2);
	}
	
	public static void main(String[] args) {
		StackDomo stackDomo = new StackDomo();
		String lamada = "";
		int jieguo = stackDomo.jisuan("7+6*5*(3*(2+2)*2-(3+11))*2-(1+3)*20",0);
		System.out.println(jieguo);
		
		String s = stackDomo.zhongToHou("7+6*5*(3*(2+2)*2-(3+11))*2-(1+3)*20");
		System.out.println(s);
		int nibolan = stackDomo.nibolan(s);
		System.out.println(nibolan);
		
		
	}
	
	//运算式计算
	public int jisuan(String s,int n){
		StackList num = new StackList(200);
		StackList fuhao = new StackList(200);
		char[] ss = s.toCharArray();
		int flag = 0;
		a = n;
		for ( ; a < ss.length ; a++ ){
			if (ss[a] == '('){
				num.push(jisuan(s, ++a) + "");
			}
			if (ss[a] == ')'){
				++a;
				break;
			}
			if (map.get(ss[a] + "") == null){
				flag++;
				if (flag > 1){
					num.push(num.pop() + ss[a]);
				}else{
					num.push(ss[a] + "");
				}
			} else {
				flag = 0;
				if (fuhao.isEmpty()){
					fuhao.push(ss[a] + "");
				} else {
					if (map.get(fuhao.lockTop()) < map.get(ss[a] + "")){
						fuhao.push(ss[a] + "");
					} else {
						yunsuan(num,fuhao);
						a--;
					}
				}
			}
		}
		while (!fuhao.isEmpty()) {
			yunsuan(num, fuhao);
		}
		return Integer.parseInt(num.pop());
	}
	
	//判断运算符进行运算
	public void yunsuan(StackList num,StackList fuhao){
		int num2 = Integer.parseInt(num.pop());
		int num1 = Integer.parseInt(num.pop());
		switch(fuhao.pop()){
			case "+" : num.push(num1 + num2 + ""); break;
			case "-" : num.push(num1 - num2 + ""); break;
			case "*" : num.push(num1 * num2 + ""); break;
			case "/" : num.push(num1 / num2 + ""); break;
		}
	}
	
	//逆波兰表达式的运算,传入一个使用空格分割的逆波兰表达式
	public int nibolan(String s){
		String[] ss = s.split(" ");
		Stack<String> stack = new Stack<>();
		for (String s1 : ss) {
			if (s1.matches("\\d+")){
				stack.push(s1);
			} else {
				int num2 = Integer.parseInt(stack.pop());
				int num1 = Integer.parseInt(stack.pop());
				switch(s1){
					case "+" : stack.push(num1 + num2 + ""); break;
					case "-" : stack.push(num1 - num2 + ""); break;
					case "*" : stack.push(num1 * num2 + ""); break;
					case "/" : stack.push(num1 / num2 + ""); break;
				}
			};
		}
		return Integer.parseInt(stack.pop());
	}
	
	//中缀表达式转后缀表达式
	public String zhongToHou(String zhong){
		//定义两个栈
		
		//1.存放数字及中间结果的栈
		/*注意:这个栈可以换成list集合或者直接字符串代替,因为在整个过程中
		此栈只用来存储,没有弹栈的操作,而且在最后还需要进行逆序,使用字符串可直接进行 += 操作*/
		StackList num = new StackList(200);
		//2.存放运算符的栈
		StackList fuhao = new StackList(200);
		//将字符串转为char数组
		char[] ss = zhong.toCharArray();
		//定义标识,用于判断数字是多位数字
		int flag = 0;
		//循环
		for (int a = 0 ; a < ss.length ; a++ ){
			//判断是否是运算符号,不是符号进入此if中
			if (map.get(ss[a] + "") == null){
				//进行标识数字的位数
				flag++;
				//判断flag > 1,标识此数字是多位数,非个位数
				if (flag > 1){
					//将原来的数字取出进行拼接在放入
					num.push(num.pop() + ss[a]);
				}else{
					//存入数字
					num.push(ss[a] + "");
				}
			} else {//不是数字
				//将标识重置
				flag = 0;
				//判断符号栈中是否为空或者栈顶符号是'('时,直接将此符号入栈
				if (fuhao.isEmpty() || fuhao.lockTop().equals("(")){
					fuhao.push(ss[a] + "");
				} else if (ss[a] == ')') {
					//遇到符号是')'时需要逆向获取到小括号中的符号,遇到符号栈中存储的'('停止,将符号存入数字中间栈中
					while (!fuhao.lockTop().equals("(")){
						num.push(fuhao.pop());
					}
					//这里的pop()的意思是上面在遇到'('时已经停止,所以栈中还有'('符号,需要将此符号出栈,废弃掉
					fuhao.pop();
				} else {
					//有符号且不是'('时,判断符号的优先级,优先级大于栈顶的符号直接进行保存
					if (map.get(fuhao.lockTop()) < map.get(ss[a] + "")){
						fuhao.push(ss[a] + "");
					} else {
						//否则需要将符号栈中存储的符号弹栈保存到中间栈中
						num.push(fuhao.pop());
						//执行a--的目的是上面只是将符号出栈,但循环中指向的符号还未做处理,
						//所以需要再走一遍流程,用来判断当前符号是继续出栈还是进行保存
						a--;
					}
				}
			}
		}
		//结束循环后在符号栈中还有剩余符号,将符号依次取出放入中间栈即可
		//结束后num栈中存储的就是逆序的逆波兰表达式(栈要从顶端取数据)
		while (!fuhao.isEmpty()) {
			num.push(fuhao.pop());
		}
		String hou = "";
		//循环num栈将数据取出并逆序进行拼接,得到的就是逆波兰表达式
		while (!num.isEmpty()){
			hou = num.pop() + " " + hou;
		}
		return hou;
	}
}

class StackList{
	//定义栈顶
	private int top;
	//定义栈底
	private int bottom;
	//数组长度
	private int maxSize;
	//定义存储数据的数组
	private String[] stack;
	
	public StackList(int size){
		if (size < 1){
			System.out.println("参数不正确!");
			return;
		}
		maxSize = size;
		stack = new String[size];
		top = -1;
		bottom = -1;
	}
	
	//判断满
	public boolean isFull(){
		return top == maxSize - 1;
	}
	
	//判断空
	public boolean isEmpty(){
		return top == bottom;
	}
	
	//添加
	public void push(String s){
		if (isFull()){
			System.out.println("栈满!");
			return;
		}
		stack[++top] = s;
	}
	
	//弹栈
	public String pop(){
		if (isEmpty()){
			System.out.println("栈空!");
			return null;
		}
		return stack[top--];
	}
	
	//遍历
	public void bianli(){
		for (int a = top ; a != bottom ; a --){
			System.out.println(stack[a]);
		}
	}
	
	//查看栈顶
	public String lockTop() {
		return stack[top];
	}
	
	
}
